- Title
- Parameterized complexity and biopolymer sequence comparison
- Creator
- Cai, Liming; Huang, Xiuzhen; Liu, Chunmei; Rosamond, Frances; Song, Yinglei
- Relation
- Computer Journal Vol. 51, Issue 3, p. 270-291
- Publisher Link
- http://dx.doi.org/10.1093/comjnl/bxm035
- Publisher
- Oxford University Press
- Resource Type
- journal article
- Date
- 2008
- Description
- The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure-sequence alignment and structure-structure alignment. Algorithm techniques, built on the structural-unit level as well as on the residue level, are discussed.
- Subject
- parameterized complexity; parameterized algorithms; pairwise sequence alignment; multiple sequence alignment; sequence-structure alignment; structure-structure alignment; tree width; tree decomposition
- Identifier
- uon:5488
- Identifier
- http://hdl.handle.net/1959.13/43368
- Identifier
- ISSN:0010-4620
- Reviewed
- Hits: 4106
- Visitors: 4010
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|